package com.zhanghp.class025;

import static com.zhanghp.common.ArrUtil.*;

/**
 * <p>堆结构和堆排序，填函数练习风格</p>
 * <a href = "https://leetcode.cn/problems/sort-an-array/">测试链接</a>
 * <p>大根堆概念：完全二叉树,任一非叶子结点都大于等于它的孩子</p>
 * <ul>
 *     i结点公式：
 *     <li>
 *          i的父亲节点：(i-1)/2
 *     </li>
 *     <li>
 *         i的左孩子：i*2 + 1
 *     </li>
 *     <li>
 *         i的右孩子：i*2 + 2
 *     </li>
 * </ul>
 * <br/>
 * <hr/>
 * <p>补充知识</p>
 * <p>
 *     非叶子结点：非叶子结点，在树形数据结构中，指的是那些至少有一个子结点的结点。它们也常被称为分支结点、内部结点或非终端结点。在二叉树结构中，非叶子结点特指那些拥有一个或两个子结点（左子结点和/或右子结点）的结点，这些结点通常用于存储中间的关键字或数据，并通过指针指向其下一级的子树。
 * 在更复杂的树结构如B+树中，非叶子结点（也称为索引结点或中间结点）通常不直接存储数据，而是存储指向其子结点的指针以及用于索引和搜索的键值。这种结构设计有助于减少磁盘I/O操作，提高数据检索效率。
 * 简单来说，如果一个结点不是叶子结点，那么它就有至少一个子结点，并且在树的数据组织和访问过程中起到连接和导航的作用
 * </p>
 *
 * @author zhanghp
 * @since 2024/3/26 16:01
 */
public class HeapSort {

    public static void main(String[] args) {
        validator(100, 10, 10, arr -> {

            heapSort(arr);
            if (!isSorted(arr)) {
                print(arr);
            }

        });
        int[] arr = {2, 1, 4, 5, 6, 1};
        heapSort(arr);
        print(arr);
    }

    /**
     * <p>向上调整</p>
     * <p>指定i位置索引，向上调整大根堆</p>
     * <p>i ∈ [0, arr.length - 1]</p>
     * <p>不能用(i - 1) >> 1 若 i为0，则算的结果是-1</p>
     *
     * @param arr 数组
     * @param i   调整索引位置
     */
    public static void heapInsert(int[] arr, int i) {
        while (arr[i] > arr[(i - 1) / 2]) {
            swap(arr, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    /**
     * <p>向下调整</p>
     * <p>指定i位置索引，向下调整大根堆</p>
     * <p>i ∈ [0, arr.length - 1]</p>
     *
     * @param arr 数组
     * @param i   调整索引位置
     */
    public static void heapify(int[] arr, int i, int size) {
        int l = (i << 1) + 1;
        while (l < size) {
            // 左孩子：l
            // 右孩子：l + 1
            // 选出最强孩子（判断右孩子是否存在 & 左右孩子值比较）
            int best = (l + 1) < size && arr[l] < arr[l + 1] ? l + 1 : l;
            // 比较父亲和最强孩子
            if (arr[i] > arr[best]) {
                break;
            }
            // 父亲与孩子交换
            swap(arr, i, best);
            // 父亲i换到最强孩子索引
            i = best;
            // 左孩子换值
            l = (i << 1) + 1;
        }
    }

    /**
     * <p>堆排序（经典版本）</p>
     * <p>
     * 从顶到底建立大根堆，O(n * logn) <br/>
     * 依次弹出堆内最大值并排好序，O(n * logn)<br/>
     * 整体时间复杂度O(n * logn)
     * </p>
     * <br/>
     * <ul>
     *     <li>
     *         向上调整，数组处理
     *     </li>
     *     <li>
     *         数组（大根堆），交换头尾
     *     </li>
     *     <li>
     *         size减小，去掉最后一位
     *     </li>
     *     <li>
     *         向下调整，重新排序为大根堆
     *     </li>
     * </ul>
     *
     * <ul>ex：[2,1,4,6,8]
     *      <li>
     *          调整大根堆：[8,2,4,6,1]
     *      </li>
     *      <li>
     *          交换：[1,2,4,6,8]
     *      </li>
     *      <li>
     *          size--
     *      </li>
     *      <li>
     *          处理:[1,2,4,6] -> [6,1,4,2]
     *      </li>
     *
     * </ul>
     *
     * @param arr
     */
    public static void heapSort(int[] arr) {
        int size = arr.length;
        // 数组 -> 大根堆 （向上调整）
        for (int i = 0; i < size; i++) {
            heapInsert(arr, i);
        }
        // 排序
        while (size > 1) {
            // 首位交换
            swap(arr, 0, --size);
            // 重新排大根堆（向下调整）
            heapify(arr, 0, size);
        }
    }

    /**
     * <p>堆排序</p>
     * <p>
     * 从底到顶建立大根堆，O(n)<br/>
     * 依次弹出堆内最大值并排好序，O(n * logn)<br/>
     * 整体时间复杂度O(n * logn)<br/>
     * </p>
     * <br/>
     * <ul>
     *     <ol>
     *
     *     </ol>
     * </ul>
     *
     * @param arr 数组
     */
    public static void heapSort2(int[] arr) {
        int n = arr.length;
        for (int i = n - 1; i >= 0; i--) {
            heapify(arr, i, n);
        }
        int size = arr.length;
        while (size > 1){
            swap(arr, 0, --size);
            heapify(arr, 0, size);
        }

    }
}
